| Программирование
магических игр Статьи | Архивы | Переводы | Ссылки | Книги | Новости |
 |
|
Основы алгоритма сжатия JPEG |
||
Алгоритм JPEG можно разделить на несколько этапов
0. Подготовка
1. ДКП (Дискретно Косинусоидальное Преобразование)
2. Квантование
3. Вторичное сжатие
-----------------------------------------------------------------------------
Этап 0. Подготовка
-----------------------------------------------------------------------------
Нужно преобразовать изображение в вид яркость/цветность, можно использовать
цветовую схему YCbCr (YUV), вот формулы перевода:
Y = 0.299*R + 0.578*G + 0.114*B
Cb = 0.1678*R - 0.3313*G + 0.5*B
Cr = 0.5*R - 0.4187*G + 0.0813*B
Y нужно сохранить без изменений, его можно сжать любым алгоритмом без потери
данных.
Теперь я попятаюсь объяснить как сжать Cb и Cr
-----------------------------------------------------------------------------
Этап 1. ДКП
-----------------------------------------------------------------------------
Следует создать ДКП матрицу, используя эту формулу
DCT = 1/sqr(N), если i=0
ij
DCT = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0
ij
N = 8, 0 < i < 7 , 0 < j < 7
в результате имеем:
|.353553 .353553 .353553 .353553 .353553 .353553 .353553 .353553|
|.490393 .415818 .277992 .097887 -.097106 -.277329 -.415375 -.490246|
|.461978 .191618 -.190882 -.461673 -.462282 -.192353 .190145 .461366|
DCT = |.414818 -.097106 -.490246 -.278653 .276667 .490710 .099448 -.414486|
|.353694 -.353131 -.354256 .352567 .354819 -.352001 -.355378 .351435|
|.277992 -.490246 .096324 .416700 -.414486 -.100228 .491013 -.274673|
|.191618 -.462282 .461366 -.189409 -.193822 .463187 -.460440 .187195|
|.097887 -.278653 .416700 -.490862 .489771 -.413593 .274008 -.092414|
например, нам нужно сжать следующий фрагмент изображения:
| 95 88 88 87 95 88 95 95|
|143 144 151 151 153 170 183 181|
|153 151 162 166 162 151 126 117|
IMG = |143 144 133 130 143 153 159 175|
|123 112 116 130 143 147 162 189|
|133 151 162 166 170 188 166 128|
|160 168 166 159 135 101 93 98|
|154 155 153 144 126 106 118 133|
|-33 -40 -40 -41 -33 -40 -33 -33|
| 15 16 23 23 25 42 55 53|
| 25 23 34 38 34 23 -2 -11|
IMG = | 15 16 5 2 15 25 31 47|
| -5 -16 -12 2 15 19 34 61|
| 5 23 34 38 42 60 38 0|
| 32 40 38 31 7 -27 -35 -30|
| 26 27 25 16 -2 -22 -10 5|
T
вот формула, по которой производится ДКП: RES*IMG*DCT
T
для начала нужно посчитать промежуточную матрицу: TMP = IMG*DCT
|-103 -3 1 2 4 0 -1 5|
| 89 -40 12 -2 -7 5 1 0|
| 57 31 -30 6 2 0 5 0|
TMP = | 55 -28 24 1 0 -8 0 0|
| 32 -60 18 -1 14 0 -8 1|
| 84 -11 -37 17 -24 4 0 -4|
| 19 81 -16 -20 8 -3 4 0|
| 22 40 11 -22 8 0 -3 2|
затем умножаем ее на ДКП матрицу: RES = TMP*DCT
| 91 3 -5 -6 2 0 1|
|-38 -57 9 17 -2 2 2|
|-80 58 0 -18 4 3 4|
RES = |-52 -36 -11 13 -9 3 0|
|-86 -40 44 -7 17 -6 4|
|-62 64 -13 -1 3 -8 0|
|-16 14 -35 17 -11 2 -1|
|-53 32 -9 -8 22 0 2|
______________________________________________________________________________
Этап 2. Квантование
------------------------------------------------------------------------------
На этом этапе мы посчитаем матрицу квантования, используя этот псевдо код:
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
Q[i][j] = 1+((1+i+j)*q);
}
где q - это коэффициент качества, от него зависит степень потери качества
сжатого изображения
для q = 2 имеем матрицу квантования:
| 3 5 7 9 11 13 15 17|
| 5 7 9 11 13 15 17 19|
| 7 9 11 13 15 17 19 21|
Q = | 9 11 13 15 17 19 21 23|
|11 13 15 17 19 21 23 25|
|13 15 17 19 21 23 25 27|
|15 17 19 21 23 25 27 29|
|17 19 21 23 25 27 29 31|
теперь нужно каждое число в матрице квантования разделить на число в
соответствущей позиции в матрице RES, в результате получим:
| 30 0 0 0 0 0 0 0|
| -7 8 1 1 0 0 0 0|
|-11 6 0 1 0 0 0 0|
A = | -5 -3 0 0 0 0 0 0|
| -7 -3 2 0 0 0 0 0|
| -4 4 0 0 0 0 0 0|
| -1 0 1 0 0 0 0 0|
| -3 1 0 0 0 0 0 0|
как вы видите здесь имеется довольно много нулей, мы получим наиболее
длинную последовательность нулей, если будем использовать следущий алгоритм:
+----+----+----+----+----+----+----+----+
| 1 | 2 | 6 | 7 | 15 | 16 | 28 | 29 |
+----+----+----+----+----+----+----+----+
| 3 | 5 | 8 | 14 | 17 | 27 | 30 | 43 |
+----+----+----+----+----+----+----+----+
| 4 | 9 | 13 | 18 | 26 | 31 | 42 | 44 |
+----+----+----+----+----+----+----+----+
| 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |
+----+----+----+----+----+----+----+----+
| 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |
+----+----+----+----+----+----+----+----+
| 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |
+----+----+----+----+----+----+----+----+
| 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |
+----+----+----+----+----+----+----+----+
| 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |
+----+----+----+----+----+----+----+----+
итак у нас получилась последовательность:
30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0
0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
для большего сжатия можно перед первым этапом JPEG можно провести
субдискретизацию, или другими словами уменьшить частоту изображения,
идея очень проста:
к примеру у нас есть следующая последовательность (Cb или Cr)
11 42 200 123 56 32 125 234 12 24 34 78 145 134 245 101
если будем использовать субдискретизацию 4:1:1 результирующая
последовательность будет:
11 123 125 24 145 101
а если использовать 4:2:2
11 234 245
а для восстановления последовательности нужно интерполироать
------------------------------------------------------------------------------
Этап 3. Вторичное сжатин
______________________________________________________________________________
На этом этапе можно применить следующие алгоритмя
a) 7bit RLE
b) LZW с кодом переменной длинны
c) Адаптированное кодирование Хаффмана
______________________________________________________________________________
a) 7bit RLE
Этот алгоритм очень прост.Если у нас есть последовательнось одинаковых байтов,
то нужно установить последний бит в 0, посчитать количество байт и записать в
оставшиеся биты. Если у нас последоваетльность различных байт, то нужно уста-
новить последний быт в 1, посчитать количество байт и записать его в оставшиеся
биты. Для нашей поледовательности получится:
133 30 0 -7 -11 8 | 2 0 | 135 1 6 -5 -7 -3 0 1 | 3 0 | 135 1 0 -3 -4 -1 4 2
11 0 | 131 -3 1 1 | 27 0
итак, мы сжали 64 байта в 34
b) LZW с кодом переменной длиины
Этот алгоритм основан на динамически формируемом словаре, который состоит из
различных строк. Строки заменяются кодами переменной длины. Вот этапы этого
алгоритма:
1. Инициализуем словарь. В нашем случае числами в диапазоне [0;255].
BITS = 9, MAX = 2^BITS = 512
2. STRING = первый символ
3. Пока не кончились символы:
4. CHARACTER = взять символ из данных
5. Если STRING+CHARACTER есть в словаре, тогда STRING = STRING+CHARACTER,
иначе выдать код для STRING, добавить STRING+CHARACTER в словарь,
если количество строк в словаре > MAX-1, тогда у величиваем BITS
и вычисляем заново MAX=2^BITS, STRING=CHARACTER
6. переход на 3
7. выдать код для STRING
теперь нам нужно сжать нашу последовательность, но сперва прибавим ко всем
значениям 128, чтобы сделать их положительными
158 128 121 117 136 128 128 129 134 123 121 125 128 129 128 128 128 129 128
125 124 127 132 130 128 128 128 128 128 128 128 128 128 128 128 125 129 129
128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128
128 128 128 128 128 128 128 128
STRING=158
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (158) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 121
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (128) и добавить STRING+CHARACTER в словарь, STRING = 121
CHARACTER = 117
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (121) и добавить STRING+CHARACTER в словарь, STRING = 117
CHARACTER = 136
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (117) и добавить STRING+CHARACTER в словарь, STRING = 136
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (136) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (128) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 129
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (128) и добавить STRING+CHARACTER в словарь, STRING = 129
CHARACTER = 134
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (129) и добавить STRING+CHARACTER в словарь, STRING = 134
CHARACTER = 123
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (134) и добавить STRING+CHARACTER в словарь, STRING = 123
CHARACTER = 121
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (123) и добавить STRING+CHARACTER в словарь, STRING = 121
CHARACTER = 125
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (121) и добавить STRING+CHARACTER в словарь, STRING = 125
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (125) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 129
STRING+CHARACTER присутствует в словаре, STRING = STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (262) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING = STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (261) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 129
STRING+CHARACTER присутствует в словаре, STRING = STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING = STRING+CHARACTER
CHARACTER = 125
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (268) и добавить STRING+CHARACTER в словарь, STRING = 125
CHARACTER = 124
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (125) и добавить STRING+CHARACTER в словарь, STRING = 124
CHARACTER = 127
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (124) и добавить STRING+CHARACTER в словарь, STRING = 127
CHARACTER = 132
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (127) и добавить STRING+CHARACTER в словарь, STRING = 132
CHARACTER = 130
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (132) и добавить STRING+CHARACTER в словарь, STRING = 130
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (130) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (269) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (276) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 125
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (276) и добавить STRING+CHARACTER в словарь, STRING = 125
CHARACTER = 129
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (125) и добавить STRING+CHARACTER в словарь, STRING = 129
CHARACTER = 129
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (129) и добавить STRING+CHARACTER в словарь, STRING = 129
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (129) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (277) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (282) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (283) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = 128
STRING+CHARACTER отсутствует в словаре, тогда нужно выдать код для
STRING (284) и добавить STRING+CHARACTER в словарь, STRING = 128
CHARACTER = 128
STRING+CHARACTER присутствует в словаре, STRING=STRING+CHARACTER
CHARACTER = EOS (конец данных)
мы достигли конца данных, нужно выдать код для STRING (261) и вот
нажа сжатая строка
158 128 121 117 136 128 128 129 134 123 121 125 262 261 268 125 124 127 132
130 269 276 276 125 129 129 277 282 283 284
у нас было 9 бит на код и мы сжали 64 байта в 35 (31*9/8)
Вот алгоритм разпаковки:
1. Инициализуем словарь. Это числа в интервале [0;255].
BITS = 9, MAX = 2^BITS = 512
2. считываем OLD_CODE
3. выписываем OLD_CODE
4. Пока не кончились коды:
5. считываем NEW_CODE
6. если NEW_CODE отсутствует в словаре тогда STRING = трансляция OLD_CODE,
STRING = STRING+CHARACTER, иначе STRING = трансляция NEW_CODE
7. выписываем STRING
8. CHARACTER = первый символ в STRING
9. добавить OLD_CODE+CHARACTER в словарь
10. Если количество строк в словаре > MAX-1, тогда увеличиваем BITS,
и вычисляем заново MAX=2^BITS
11. OLD_CODE = NEW_CODE
12. идем на 4
теперь давайте распакуем нашу последовательность
OLD_CODE = 158
ouput 158
NEW_CODE = 128
NEW_CODE присутствует в словаре, тогда STRING = 128
выдаем STRING
CHARACTER = 128
добавляем "158 128" в словарь
OLD_CODE = 128
NEW_CODE = 121
NEW_CODE присутствует в словаре, тогда STRING = 121
выдаем STRING
CHARACTER = 121
добавляем "128 121" в словарь
OLD_CODE = 121
NEW_CODE = 117
NEW_CODE присутствует в словаре, тогда STRING = 117
выдаем STRING
CHARACTER = 117
добавляем "121 117" в словарь
OLD_CODE = 117
NEW_CODE = 136
NEW_CODE присутствует в словаре, тогда STRING = 136
выдаем STRING
CHARACTER = 136
добавляем "117 136" в словарь
OLD_CODE = 136
NEW_CODE = 128
NEW_CODE присутствует в словаре, тогда STRING = 128
выдаем STRING
CHARACTER = 128
добавляем "136 128" в словарь
OLD_CODE = 128
NEW_CODE = 128
NEW_CODE присутствует в словаре, тогда STRING = 128
выдаем STRING
CHARACTER = 128
добавляем "128 128" в словарь
OLD_CODE = 128
NEW_CODE = 129
NEW_CODE присутствует в словаре, тогда STRING = 129
выдаем STRING
CHARACTER = 129
добавляем "128 129" в словарь
OLD_CODE = 129
NEW_CODE = 134
NEW_CODE присутствует в словаре, тогда STRING = 134
выдаем STRING
CHARACTER = 134
добавляем "129 134" в словарь
OLD_CODE = 134
NEW_CODE = 123
NEW_CODE присутствует в словаре, тогда STRING = 123
выдаем STRING
CHARACTER = 123
добавляем "134 123" в словарь
OLD_CODE = 123
NEW_CODE = 121
NEW_CODE присутствует в словаре, тогда STRING = 121
выдаем STRING
CHARACTER = 121
добавляем "123 121" в словарь
OLD_CODE = 121
NEW_CODE = 125
NEW_CODE присутствует в словаре, тогда STRING = 125
выдаем STRING
CHARACTER = 125
добавляем "121 125" в словарь
OLD_CODE = 125
NEW_CODE = 262
NEW_CODE присутствует в словаре, тогда STRING = "128 129"
выдаем STRING
CHARACTER = 128
добавляем "125 128" в словарь
OLD_CODE = 262
NEW_CODE = 261
NEW_CODE присутствует в словаре, тогда STRING = "128 128"
выдаем STRING
CHARACTER = 128
добавляем "128 129 128" в словарь
OLD_CODE = 261
NEW_CODE = 268
NEW_CODE присутствует в словаре, тогда STRING = "128 129 128"
выдаем STRING
CHARACTER = 128
добавляем "128 128 128" в словарь
OLD_CODE = 268
NEW_CODE = 125
NEW_CODE присутствует в словаре, тогда STRING = 125
выдаем STRING
CHARACTER = 125
добавляем "128 129 128 125" в словарь
OLD_CODE = 125
NEW_CODE = 124
NEW_CODE присутствует в словаре, тогда STRING = 124
выдаем STRING
CHARACTER = 124
добавляем "125 124" в словарь
OLD_CODE = 124
NEW_CODE = 127
NEW_CODE присутствует в словаре, тогда STRING = 127
выдаем STRING
CHARACTER = 127
добавляем "124 127" в словарь
OLD_CODE = 127
NEW_CODE = 132
NEW_CODE присутствует в словаре, тогда STRING = 132
выдаем STRING
CHARACTER = 132
добавляем "127 132" в словарь
OLD_CODE = 132
NEW_CODE = 130
NEW_CODE присутствует в словаре, тогда STRING = 130
выдаем STRING
CHARACTER = 130
добавляем "132 130" в словарь
OLD_CODE = 130
NEW_CODE = 269
NEW_CODE присутствует в словаре, тогда STRING = "128 128 128"
выдаем STRING
CHARACTER = 128
добавляем "130 128" в словарь
OLD_CODE = 269
NEW_CODE = 276
NEW_CODE отсутствует в словаре, тогда STRING = "128 128 128"
and STRING=STRING+CHARACTER
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128" в словарь
OLD_CODE = 276
NEW_CODE = 276
NEW_CODE присутствует в словаре, тогда STRING = "128 128 128 128"
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128 128" в словарь
OLD_CODE = 276
NEW_CODE = 125
NEW_CODE присутствует в словаре, тогда STRING = 125
выдаем STRING
CHARACTER = 125
добавляем "128 128 128 128 125" в словарь
OLD_CODE = 125
NEW_CODE = 129
NEW_CODE присутствует в словаре, тогда STRING = 129
выдаем STRING
CHARACTER = 129
добавляем "125 129" в словарь
OLD_CODE = 129
NEW_CODE = 129
NEW_CODE присутствует в словаре, тогда STRING = 129
выдаем STRING
CHARACTER = 129
добавляем "129 129" в словарь
OLD_CODE = 129
NEW_CODE = 277
NEW_CODE присутствует в словаре, тогда STRING = "128 128 128 128 128"
выдаем STRING
CHARACTER = 128
добавляем "129 128" в словарь
OLD_CODE = 277
NEW_CODE = 282
NEW_CODE отсутствует в словаре, тогда STRING = "128 128 128 128 128"
and STRING=STRING+CHARACTER
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128 128 128" в словарь
OLD_CODE = 282
NEW_CODE = 283
NEW_CODE отсутствует в словаре, тогда STRING = "128 128 128 128 128 128"
and STRING=STRING+CHARACTER
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128 128 128 128" в словарь
OLD_CODE = 283
NEW_CODE = 284
NEW_CODE отсутствует в словаре, тогда STRING = "128 128 128 128 128 128 128"
and STRING=STRING+CHARACTER
выдаем STRING
CHARACTER = 128
добавляем "128 128 128 128 128 128 128 128" в словарь
OLD_CODE = 284
итак у нас искомая последоваетльность, это работает! :))) |
c) Адаптирование кодирование Хаффмана
Этот алгоритм основывается на частотах появления символов, и более часто
повторяющийся символ представляется более малым кодом
Вот алгоритм:
1. Инициализуем частоты - 1 для каждого символа
2. Строим дерево, символы с меньшей частотой мы объединяем в один узел
3. Пока есть символы:
4. ищем символ в дереве, если идем направо выдаем 1, иначе 0
(конечно в битах)
5. увеличиваем частоту символа и перестраиваем дерево
6. переходим к 3
теперь попытаемя закодировать нашу последовательность, сперва нам нужно добавить
128, чтобы сделать все значения положительными:
158 128 121 117 136 128 128 129 134 123 121 125 128 129 128 128 128 129 128
125 124 127 132 130 128 128 128 128 128 128 128 128 128 128 128 125 129 129
128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128
128 128 128 128 128 128 128 128
для упрощения объяснения мы предполагаем, что все возможные символы это:
158 128 121 117 136 129 134 123 125 124 127 132 130
(от 0 до 256 по-настоящему)
итак в начале у нас имеются частоты:
158 - 1, 128 - 1, 121 - 1, 117 - 1, 136 - 1, 129 - 1, 134 - 1, 123 - 1,
125 - 1, 124 - 1, 127 - 1, 132 - 1, 130 - 1
и дерево:
/------------13----------\
I I
/-------8-------\ /----5-----\
I I I I
/---4---\ /---4---\ I /--3--\
I I I I I I I
/-2-\ /-2-\ /-2-\ /-2-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
1 1 1 1 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=158
для него код будет 1111
теперь частота CHARACTER будет 2, теперь перестроим дерево
/------------14-------------\
I I
/-------8------\ /----6------\
I I I I
/--4--\ /---4---\ /---4---\ I
I I I I I I I
I /-2-\ /-2-\ /-2-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
2 1 1 1 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=128
для него код будет 1101
теперь частота CHARACTER будет 2, теперь перестроим дерево
/-------------15-------------\
I I
/-----8-----\ /------7-------\
I I I I
I /---4---\ /---4---\ /--3--\
I I I I I I I
/-4-\ /-2-\ /-2-\ /-2-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
2 2 1 1 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=121
для него код будет 1011
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------------16----------\
I I
/----8---\ /-------8-------\
I I I I
I /--4--\ /---4---\ /---4---\
I I I I I I I
/-4-\ I /-2-\ /-2-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
2 2 2 1 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=117
для него код будет 1001
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------------16----------\
I I
I /----------9-----\
I I I
I I /----5-----\
I I I I
/---8---\ /---4---\ I /--3--\
I I I I I I I
/-4-\ /-4-\ /-2-\ /-2-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
2 2 2 2 1 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=136
для него код будет 0111
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------------18-------\
I I
I /----------10-------\
I I I
I I /----6------\
I I I I
/---8---\ /--4--\ /---4---\ I
I I I I I I I
/-4-\ /-4-\ I /-2-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
2 2 2 2 2 1 1 1 1 1 1 1 1
158 128 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=128
для него код будет 110
теперь частота CHARACTER будет 3, теперь перестроим дерево
/-------------19-----------\
I I
I /--------12----------\
I I I
I /------8----\ I
I I I I
/--7--\ I /---4---\ /---4---\
I I I I I I I
I /-4-\ /-4-\ /-2-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
3 2 2 2 2 1 1 1 1 1 1 1 1
128 158 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=129
для него код будет 01011
теперь частота CHARACTER будет 2, теперь перестроим дерево
/-------------20-----------\
I I
I /-----------13--------\
I I I
I /---8----\ /-----5----\
I I I I I
/--7--\ I /--4--\ I /--3--\
I I I I I I I I
I /-4-\ /-4-\ I /-2-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
3 2 2 2 2 2 1 1 1 1 1 1 1
128 158 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=134
для него код будет 01001
теперь частота CHARACTER будет 2, теперь перестроим дерево
/-------------21-----------\
I I
I /-----------14--------\
I I I
I I /-----6-----\
I I I I
/--7--\ /---8---\ /---4---\ I
I I I I I I I
I /-4-\ /-4-\ /-4-\ /-2-\ /-2-\ /-2-\
I I I I I I I I I I I I I
3 2 2 2 2 2 2 1 1 1 1 1 1
128 158 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=123
для него код будет 00111
теперь частота CHARACTER будет 2, теперь перестроим дерево
/-------------22-----------\
I I
I /-----------15------\
I I I
I I /------7------\
I I I I
/--7--\ /---8---\ /--4--\ /--3--\
I I I I I I I I
I /-4-\ /-4-\ /-4-\ I /-2-\ /-2-\ I
I I I I I I I I I I I I I
3 2 2 2 2 2 2 2 1 1 1 1 1
128 158 121 117 136 129 134 123 125 124 127 132 130
CHARACTER=121
для него код будет 00111
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------23-----------\
I I
I /---9-------\
I I I
/-----14----\ I /---5------\
I I I I I
I /---8---\ I I /--3--\
I I I I I I I
/-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\ I
I I I I I I I I I I I I I
3 3 2 2 2 2 2 2 1 1 1 1 1
128 121 158 117 136 129 134 123 125 124 127 132 130
CHARACTER=125
для него код будет 0011
теперь частота CHARACTER будет 2, теперь перестроим дерево
/--------24-----------\
I I
I /---10-------\
I I I
/-----14----\ I /---6------\
I I I I I
I /---8---\ I /--4--\ I
I I I I I I I
/-6-\ /-4-\ /-4-\ /-4-\ I /-2-\ /-2-\
I I I I I I I I I I I I I
3 3 2 2 2 2 2 2 2 1 1 1 1
128 121 158 117 136 129 134 123 125 124 127 132 130
CHARACTER=128
для него код будет 111
теперь частота CHARACTER будет 4, теперь перестроим дерево
/--------25-----------\
I I
I /---10-------\
I I I
/-----15----\ I /---6------\
I I I I I
I /---8---\ I /--4--\ I
I I I I I I I
/-7-\ /-4-\ /-4-\ /-4-\ I /-2-\ /-2-\
I I I I I I I I I I I I I
4 3 2 2 2 2 2 2 2 1 1 1 1
128 121 158 117 136 129 134 123 125 124 127 132 130
CHARACTER=129
для него код будет 1000
теперь частота CHARACTER будет 3, теперь перестроим дерево
/----------26----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-10--\ /---8---\ I /---4---\
I I I I I I I
I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
4 3 3 2 2 2 2 2 2 1 1 1 1
128 121 129 158 117 136 134 123 125 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 5, теперь перестроим дерево
/----------27----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-11--\ /---8---\ I /---4---\
I I I I I I I
I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
5 3 3 2 2 2 2 2 2 1 1 1 1
128 121 129 158 117 136 134 123 125 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 6, теперь перестроим дерево
/----------28----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-12--\ /---8---\ I /---4---\
I I I I I I I
I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
6 3 3 2 2 2 2 2 2 1 1 1 1
128 121 129 158 117 136 134 123 125 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 7, теперь перестроим дерево
/----------29----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-13--\ /---8---\ I /---4---\
I I I I I I I
I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
7 3 3 2 2 2 2 2 2 1 1 1 1
128 121 129 158 117 136 134 123 125 124 127 132 130
CHARACTER=129
для него код будет 100
теперь частота CHARACTER будет 4, теперь перестроим дерево
/----------30----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-14--\ /---8---\ I /---4---\
I I I I I I I
I /-7-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
7 4 3 2 2 2 2 2 2 1 1 1 1
128 129 121 158 117 136 134 123 125 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 8, теперь перестроим дерево
/----------31----------\
I I
I /------16--------\
I I I
I I /----8------\
I I I I
/-15--\ /---8---\ I /---4---\
I I I I I I I
I /-7-\ /-4-\ /-4-\ /-4-\ /-2-\ /-2-\
I I I I I I I I I I I I I
8 4 3 2 2 2 2 2 2 1 1 1 1
128 129 121 158 117 136 134 123 125 124 127 132 130
CHARACTER=125
для него код будет 0010
теперь частота CHARACTER будет 3, теперь перестроим дерево
/---------32---------------\
I I
I /-------14--------\
I I I
/--18-\ I /----6-----\
I I I I I
I /-10--\ /---8---\ /--4--\ I
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ I /-2-\ /-2-\
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 1 1 1 1
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=124
для него код будет 00101
теперь частота CHARACTER будет 2, теперь перестроим дерево
/---------33---------------\
I I
I /-------15--------\
I I I
/--18-\ I /-----7----\
I I I I I
I /-10--\ /---8---\ I /--3--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-2-\ I
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 2 1 1 1
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=127
для него код будет 00011
теперь частота CHARACTER будет 2, теперь перестроим дерево
/---------34---------------\
I I
I /-------16--------\
I I I
/--18-\ I /-----8--\
I I I I I
I /-10--\ /---8---\ I /--4--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ I /-2-\
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 2 2 1 1
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=132
для него код будет 00001
теперь частота CHARACTER будет 2, теперь перестроим дерево
/---------35---------------\
I I
I /-------17--------\
I I I
/--18-\ I /-----9--\
I I I I I
I /-10--\ /---8---\ I /--5--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ I /-3-\
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 2 2 2 1
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=130
для него код будет 00000
теперь частота CHARACTER будет 2, теперь перестроим дерево
/---------36---------------\
I I
I /-------18--------\
I I I
/--18-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
8 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 9, теперь перестроим дерево
/---------37---------------\
I I
I /-------18--------\
I I I
/--19-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
9 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 10, теперь перестроим дерево
/---------38---------------\
I I
I /-------18--------\
I I I
/--20-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
10 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 11, теперь перестроим дерево
/---------39---------------\
I I
I /-------18--------\
I I I
/--21-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
11 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 12, теперь перестроим дерево
/---------40---------------\
I I
I /-------18--------\
I I I
/--22-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
12 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 13, теперь перестроим дерево
/---------41---------------\
I I
I /-------18--------\
I I I
/--23-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
13 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 14, теперь перестроим дерево
/---------42---------------\
I I
I /-------18--------\
I I I
/--24-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
14 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 15, теперь перестроим дерево
/---------43---------------\
I I
I /-------18--------\
I I I
/--25-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
15 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 16, теперь перестроим дерево
/---------44---------------\
I I
I /-------18--------\
I I I
/--26-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
16 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 17, теперь перестроим дерево
/---------45---------------\
I I
I /-------18--------\
I I I
/--27-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
17 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 18, теперь перестроим дерево
/---------46---------------\
I I
I /-------18--------\
I I I
/--28-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
18 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 19, теперь перестроим дерево
/---------47---------------\
I I
I /-------18--------\
I I I
/--29-\ I /-----10---\
I I I I I
I /-10--\ /---8---\ I /--6--\
I I I I I I I I
I I /-6-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
19 4 3 3 2 2 2 2 2 2 2 2 2
128 129 121 125 158 117 136 134 123 124 127 132 130
CHARACTER=125
для него код будет 1000
теперь частота CHARACTER будет 4, теперь перестроим дерево
/---------48---------------\
I I
I /-------18--------\
I I I
/--30-\ I /-----10---\
I I I I I
I /-11--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
19 4 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=129
для него код будет 101
теперь частота CHARACTER будет 5, теперь перестроим дерево
/---------49---------------\
I I
I /-------18--------\
I I I
/--31-\ I /-----10---\
I I I I I
I /-12--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
19 5 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=129
для него код будет 101
теперь частота CHARACTER будет 6, теперь перестроим дерево
/---------50---------------\
I I
I /-------18--------\
I I I
/--32-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
19 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 20, теперь перестроим дерево
/---------51---------------\
I I
I /-------18--------\
I I I
/--33-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
20 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 21, теперь перестроим дерево
/---------52---------------\
I I
I /-------18--------\
I I I
/--34-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
21 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 22, теперь перестроим дерево
/---------53---------------\
I I
I /-------18--------\
I I I
/--35-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
22 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 23, теперь перестроим дерево
/---------54---------------\
I I
I /-------18--------\
I I I
/--36-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
23 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 24, теперь перестроим дерево
/---------55---------------\
I I
I /-------18--------\
I I I
/--37-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
24 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 25, теперь перестроим дерево
/---------56---------------\
I I
I /-------18--------\
I I I
/--38-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
25 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 26, теперь перестроим дерево
/---------57---------------\
I I
I /-------18--------\
I I I
/--39-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
26 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 27, теперь перестроим дерево
/---------58---------------\
I I
I /-------18--------\
I I I
/--40-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
27 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 28, теперь перестроим дерево
/---------59---------------\
I I
I /-------18--------\
I I I
/--41-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
28 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 29, теперь перестроим дерево
/---------60---------------\
I I
I /-------18--------\
I I I
/--42-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
29 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 30, теперь перестроим дерево
/---------61---------------\
I I
I /-------18--------\
I I I
/--43-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
30 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 31, теперь перестроим дерево
/---------62---------------\
I I
I /-------18--------\
I I I
/--44-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
31 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 32, теперь перестроим дерево
/---------63---------------\
I I
I /-------18--------\
I I I
/--45-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
32 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 33, теперь перестроим дерево
/---------64---------------\
I I
I /-------18--------\
I I I
/--46-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
33 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 34, теперь перестроим дерево
/---------65---------------\
I I
I /-------18--------\
I I I
/--47-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
34 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 35, теперь перестроим дерево
/---------66---------------\
I I
I /-------18--------\
I I I
/--48-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
35 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 36, теперь перестроим дерево
/---------67---------------\
I I
I /-------18--------\
I I I
/--49-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
36 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 37, теперь перестроим дерево
/---------68---------------\
I I
I /-------18--------\
I I I
/--50-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
37 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 38, теперь перестроим дерево
/---------69---------------\
I I
I /-------18--------\
I I I
/--51-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
38 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 39, теперь перестроим дерево
/---------70---------------\
I I
I /-------18--------\
I I I
/--52-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
39 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 40, теперь перестроим дерево
/---------71---------------\
I I
I /-------18--------\
I I I
/--53-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
40 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 41, теперь перестроим дерево
/---------72---------------\
I I
I /-------18--------\
I I I
/--54-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
41 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 42, теперь перестроим дерево
/---------73---------------\
I I
I /-------18--------\
I I I
/--55-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
42 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 43, теперь перестроим дерево
/---------74---------------\
I I
I /-------18--------\
I I I
/--56-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
43 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 44, теперь перестроим дерево
/---------75---------------\
I I
I /-------18--------\
I I I
/--57-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
44 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 45, теперь перестроим дерево
/---------76---------------\
I I
I /-------18--------\
I I I
/--58-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
45 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
CHARACTER=128
для него код будет 11
теперь частота CHARACTER будет 46, теперь перестроим дерево
/---------77---------------\
I I
I /-------18--------\
I I I
/--59-\ I /-----10---\
I I I I I
I /-13--\ /---8---\ I /--6--\
I I I I I I I I
I I /-7-\ /-4-\ /-4-\ /-4-\ /-4-\ I
I I I I I I I I I I I I I
46 6 4 3 2 2 2 2 2 2 2 2 2
128 129 125 121 158 117 136 134 123 124 127 132 130
теперь посмотрим что у нас получилось
/-------\ /-------\ /--------\/-------\/--------\/--------\/--------\ /----
1111 1101 1011 1001 0111 110 01011 01001 00111 00111 0011 111 1000 11 11 11
----\/--------\/--------\/-------\/----------\/----------\/----------\/--
100 11 0010 00101 00011 00001 00000 11 11 11 11 11 11 11 11 11 11 11 1000
-----\/----------\/----------\/----------\/----------\/----------\/---------
101 101 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
\/---------
11 11 11 11
итак мы сжали 64 байта в 22 (175/8 bits)
------------------------------------------------------------------------------
Вот и все!
Как достать автора:
Денис Бухаров (White Eagle)
wheagle@irex.urc.ac.ru
Россия, Челябинск
7-3512-170255
|
||
PMG 25 Февраля 1999 (c) Денис Бухаров (White Eagle) |